package com.mdnote.practice.generic_recursion;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/15
 * @description 括号生成
 */
public class LeetCode22 {

    public static void main(String[] args) {
        LeetCode22 leetCode22 = new LeetCode22();
        List<String> list = leetCode22.generateParenthesis(3);
        list.forEach(System.out::println);
    }

    /**
     * 生成括号
     * @param n 括号对数
     * @return 所有可能性
     */
    public List<String> generateParenthesis(int n) {
        // 递归法
        List<String> list = new ArrayList<>();
        recursion(0, n * 2, "", 0, 0, list);

        return list;
    }

    private void recursion(int level, int maxLevel, String res, int leftCount, int rightCount, List<String> list) {
        // Terminator
        if (level == maxLevel) {
            list.add(res);
        }
        // process current logic
        // drill down
        // 有个规则，当前左边括号一定要大于等于右边的括号
        if (leftCount >= rightCount && leftCount < maxLevel / 2) {
            recursion(level + 1, maxLevel, res + "(", leftCount + 1, rightCount, list);
        }
        if (rightCount < maxLevel / 2) {
            recursion(level + 1, maxLevel, res + ")", leftCount, rightCount+ + 1, list);
        }
        // restore current data
    }
}
